iT邦幫忙

2021 iThome 鐵人賽

DAY 15
0
Security

學密碼學也猜不到你的手機密碼系列 第 15

DAY 15- 《公鑰密碼》-ECC 橢圓曲線密碼學

  • 分享至 

  • xImage
  •  

高中聽過有人唸ㄙㄨㄟˊ 圓形,我當時真是害怕極了。

---

橢圓曲線 (Elliptic curve)

要提到密碼學不可不提的就是橢圓曲線密碼學。
這個橢圓不是普通的橢圓,甚至有長得不像橢圓。
先來看這個橢圓曲線。

這個橢圓曲線叫做secp256k1,是用來建構比特幣公私鑰的橢圓曲線。
橢圓曲線會是一個方程式,形如 https://chart.googleapis.com/chart?cht=tx&chl=y%5E2%20%3Dx%5E3%2Bax%2Bb

像secp256k1的方程式是 https://chart.googleapis.com/chart?cht=tx&chl=y%5E2%20%3Dx%5E3%2B7

一個橢圓曲線要怎麼創造公私鑰,想出這個的人腦袋真的壞掉。
我看著這個圖形只覺得他長得好像鑰匙孔。

運算

是這樣的,我們先給定圖形上的一個點 P,
接著取一個倍數 a。
這時 aP 就會對應到圖形上的另外一個點(有夠神奇)。
而當 a 到達一定大小時,aP這個點就會消失在這個圖形上,
而這個點我們稱為無窮遠點 point at infinity(https://chart.googleapis.com/chart?cht=tx&chl=%5Ctheta),此時的 a 稱為 order,寫作 「#E」。

上面看到的圖形是在實數中定義的橢圓曲線,
而我們要使用的是定義在質數體上的橢圓曲線。
簡單來說,就是在https://chart.googleapis.com/chart?cht=tx&chl=%20y%5E2%20%3Dx%5E3%2B7 mod p,
其中 p 是大於 3 的質數。

橢圓曲線有一些運算性質

1. 負號

若 P =(x, y), 則-P=(x, -y)

2 單位元

https://chart.googleapis.com/chart?cht=tx&chl=P%2B%5Ctheta%3D%5Ctheta%2BP%3DP

3 加法

如果P和Q是橢圓曲線上的兩個點
那麼P+Q就會是將兩個點相連之後對x軸做鏡射的那個點

假設https://chart.googleapis.com/chart?cht=tx&chl=P%3D(x_1%2C%20y_1)https://chart.googleapis.com/chart?cht=tx&chl=Q%3D(x_2%2C%20y_2)https://chart.googleapis.com/chart?cht=tx&chl=P%2BQ%3DR%3D(x_3%2Cy_3)
首先要先算出 PQ線 的斜率 s 。
https://chart.googleapis.com/chart?cht=tx&chl=s%3D%20%5Cfrac%7By_2-y_1%7D%7Bx_2-x_1%7D(mod%20p)
https://chart.googleapis.com/chart?cht=tx&chl=x_3%20%3Ds%5E2-x_1-x_2(modp)
https://chart.googleapis.com/chart?cht=tx&chl=y_3%20%3D%20s(x_1-x_3)-y_1

4 倍數

在橢圓曲線上做倍數的概念,
是找到P 的切線和曲線相較的點對 x 做鏡射。

https://chart.googleapis.com/chart?cht=tx&chl=s%3D%20%5Cfrac%7B3x_1%5E2%2Ba%7D%7B2y_1%7D(mod%20p)
https://chart.googleapis.com/chart?cht=tx&chl=x_3%20%3Ds%5E2-2x_1(mod%20p)
https://chart.googleapis.com/chart?cht=tx&chl=y_3%20%3D%20s(x_1-x_3)-y_1

運用以上所講的四個運算,就可以在橢圓曲線找出我們所需要的點。
而真正使用的 aP 也可以用加法跟倍數做出來。

舉個例子好了,
現在我們有一個曲線https://chart.googleapis.com/chart?cht=tx&chl=y%5E2%3Dx%5E3%2B4x%2B20 (mod17),

給定點P ( 8, 10 )。
經由運算你可以算出2P=(0, 22)
還可以一直算下去

3P = (16,2)
4P = (6,17)
5P = (20,3)
6P = (10,25)
7P = (2,6)
8P = (13,6)
...
34P = (16,27)
35P = (0,7)
36P = (8,19)
37P = $\theta$

算到最後一個36P+P的時候
因為斜率不存在,我們就說他的結果是無窮遠點。

我當然不是用手算的,下面會附上簡單的程式碼。
不過因為數字簡單,我簡陋的程式碼也有辦法算出來,
如果是數字很大的運算,電腦會直接卡住哦。
如果要加快電腦運算,需要用到其他方法來加速。

Hasse's Theorem

橢圓曲線密碼學在公鑰密碼學上的安全性,
取決於橢圓離散問題(ECDLP)的困難度。
也就是給定兩個點 T 和 P,問你「T= aP」 中, a 等於多少。

從上面的例子你可以知道,要想知道 a 是多少,基本上就只能把全部算出來找。
所以可以把 a 作為私鑰,T 作為公鑰。

已前面的secp256k1的例子來說:
在p = https://chart.googleapis.com/chart?cht=tx&chl=%202%5E%7B256%7D%20-%202%5E%7B32%7D%20-%202%5E9%20-%202%5E8%20-%202%5E7%20-%202%5E6%20-%202%5E4%20-%201之下
這個曲線上可以使用的點的數量以十六進位寫是
FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE BAAEDCE6 AF48A03B BFD25E8C D0364141

根本不可能一個一個算出來。

Hasse's 定理是用來大略計算橢圓曲線的 order 。

內涵如下:

https://chart.googleapis.com/chart?cht=tx&chl=p%2B1-2%5Csqrt%7Bp%7D%20≦ #E ≦ https://chart.googleapis.com/chart?cht=tx&chl=p%2B1%2B2%20%5Csqrt%7Bp%7D
也就是曲線上的點大約會跟質數 p 的位元一樣。
Order的大小,也攸關著橢圓曲線密碼的安全性。

圖片來源:
https://wiki.bitcoinsv.io/index.php/Secp256k1
https://gist.github.com/kanhavishva/6e86e43f107dc657e0dddd7fcddc3420

參考資料:
https://en.bitcoin.it/wiki/Secp256k1


上一篇
DAY 14- 《公鑰密碼》-RSA(2)
下一篇
DAY 16- DHKE、ECDH、ElGamal
系列文
學密碼學也猜不到你的手機密碼30
圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言